home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Graphics⁄Sound / RTrace-1.0-src / intersec.c < prev    next >
Text File  |  1992-10-28  |  22KB  |  650 lines
  1. /*
  2.  * Copyright (c) 1988, 1992 Antonio Costa, INESC-Norte.
  3.  * All rights reserved.
  4.  *
  5.  * Code, ideas or suggestions were taken from the following people:
  6.  *
  7.  *  Roman Kuchkuda      - basic ray tracer
  8.  *  Mark VandeWettering - MTV ray tracer
  9.  *  Augusto Sousa       - overall, shading model
  10.  *  Paulo Almeida       - improvements
  11.  *
  12.  * Redistribution and use in source and binary forms are permitted
  13.  * provided that the above copyright notice and this paragraph are
  14.  * duplicated in all such forms and that any documentation,
  15.  * advertising materials, and other materials related to such
  16.  * distribution and use acknowledge that the software was developed
  17.  * by Antonio Costa, at INESC-Norte. The name of the author and
  18.  * INESC-Norte may not be used to endorse or promote products derived
  19.  * from this software without specific prior written permission.
  20.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  21.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  22.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  23.  */
  24. #include "defs.h"
  25. #include "extern.h"
  26.  
  27. /**********************************************************************
  28.  *    RAY TRACING - Intersect - Version 7.3                           *
  29.  *                                                                    *
  30.  *    MADE BY    : Antonio Costa, INESC-Norte, October 1988           *
  31.  *    ADAPTED BY : Antonio Costa, INESC-Norte, June 1989              *
  32.  *    MODIFIED BY: Antonio Costa, INESC-Norte, June 1992              *
  33.  **********************************************************************/
  34.  
  35. /***** Intersect objects *****/
  36. #define CHECK_SMALLER(p1, p2, v1, v2)\
  37. do {\
  38.   if (((p1) < (p2)) OR((p1) * (v2) < (p2) * (v1)))\
  39.     return FALSE;\
  40. } while (0)
  41. #define CHECK_BIGGER(p1, p2, v1, v2)\
  42. do {\
  43.   if ((p1) * (v2) > (p2) * (v1))\
  44.     return FALSE;\
  45. } while (0)
  46. boolean
  47. octant_intersect(octant, position, vector, min, max)
  48.   int             octant;
  49.   REG xyz_ptr     position, vector, min, max;
  50. {
  51.   REG real        t1, t2;
  52.  
  53.   REALINC(octant_tests);
  54.   switch (octant)
  55.   {
  56.   case 0:
  57.     if ((min->x >= position->x) OR(min->y >= position->y)
  58.         OR(min->z >= position->z))
  59.       return FALSE;
  60.     if ((vector->x <= vector->y) AND(vector->x <= vector->z))
  61.     {
  62.       t1 = -(min->x - position->x);
  63.       t2 = -(max->y - position->y);
  64.       CHECK_SMALLER(t1, t2, -vector->x, -vector->y);
  65.       t2 = -(max->z - position->z);
  66.       CHECK_SMALLER(t1, t2, -vector->x, -vector->z);
  67.       t1 = -(max->x - position->x);
  68.       t2 = -(min->y - position->y);
  69.       CHECK_BIGGER(t1, t2, -vector->x, -vector->y);
  70.       t2 = -(min->z - position->z);
  71.       CHECK_BIGGER(t1, t2, -vector->x, -vector->z);
  72.       return TRUE;
  73.     } else
  74.     if ((vector->y <= vector->x) AND(vector->y <= vector->z))
  75.     {
  76.       t1 = -(min->y - position->y);
  77.       t2 = -(max->x - position->x);
  78.       CHECK_SMALLER(t1, t2, -vector->y, -vector->x);
  79.       t2 = -(max->z - position->z);
  80.       CHECK_SMALLER(t1, t2, -vector->y, -vector->z);
  81.       t1 = -(max->y - position->y);
  82.       t2 = -(min->x - position->x);
  83.       CHECK_BIGGER(t1, t2, -vector->y, -vector->x);
  84.       t2 = -(min->z - position->z);
  85.       CHECK_BIGGER(t1, t2, -vector->y, -vector->z);
  86.       return TRUE;
  87.     } else
  88.     {
  89.       t1 = -(min->z - position->z);
  90.       t2 = -(max->x - position->x);
  91.       CHECK_SMALLER(t1, t2, -vector->z, -vector->x);
  92.       t2 = -(max->y - position->y);
  93.       CHECK_SMALLER(t1, t2, -vector->z, -vector->y);
  94.       t1 = -(max->z - position->z);
  95.       t2 = -(min->x - position->x);
  96.       CHECK_BIGGER(t1, t2, -vector->z, -vector->x);
  97.       t2 = -(min->y - position->y);
  98.       CHECK_BIGGER(t1, t2, -vector->z, -vector->y);
  99.       return TRUE;
  100.     }
  101.   case 1:
  102.     if ((max->x < position->x) OR(min->y >= position->y)
  103.         OR(min->z >= position->z))
  104.       return FALSE;
  105.     if ((-vector->x <= vector->y) AND(-vector->x <= vector->z))
  106.     {
  107.       t1 = max->x - position->x;
  108.       t2 = -(max->y - position->y);
  109.       CHECK_SMALLER(t1, t2, vector->x, -vector->y);
  110.       t2 = -(max->z - position->z);
  111.       CHECK_SMALLER(t1, t2, vector->x, -vector->z);
  112.       t1 = min->x - position->x;
  113.       t2 = -(min->y - position->y);
  114.       CHECK_BIGGER(t1, t2, vector->x, -vector->y);
  115.       t2 = -(min->z - position->z);
  116.       CHECK_BIGGER(t1, t2, vector->x, -vector->z);
  117.       return TRUE;
  118.     } else
  119.     if ((vector->y <= -vector->x) AND(vector->y <= vector->z))
  120.     {
  121.       t1 = -(min->y - position->y);
  122.       t2 = min->x - position->x;
  123.       CHECK_SMALLER(t1, t2, -vector->y, vector->x);
  124.       t2 = -(max->z - position->z);
  125.       CHECK_SMALLER(t1, t2, -vector->y, -vector->z);
  126.       t1 = -(max->y - position->y);
  127.       t2 = max->x - position->x;
  128.       CHECK_BIGGER(t1, t2, -vector->y, vector->x);
  129.       t2 = -(min->z - position->z);
  130.       CHECK_BIGGER(t1, t2, -vector->y, -vector->z);
  131.       return TRUE;
  132.     } else
  133.     {
  134.       t1 = -(min->z - position->z);
  135.       t2 = min->x - position->x;
  136.       CHECK_SMALLER(t1, t2, -vector->z, vector->x);
  137.       t2 = -(max->y - position->y);
  138.       CHECK_SMALLER(t1, t2, -vector->z, -vector->y);
  139.       t1 = -(max->z - position->z);
  140.       t2 = max->x - position->x;
  141.       CHECK_BIGGER(t1, t2, -vector->z, vector->x);
  142.       t2 = -(min->y - position->y);
  143.       CHECK_BIGGER(t1, t2, -vector->z, -vector->y);
  144.       return TRUE;
  145.     }
  146.   case 2:
  147.     if ((min->x >= position->x) OR(max->y < position->y)
  148.         OR(min->z >= position->z))
  149.       return FALSE;
  150.     if ((vector->x <= -vector->y) AND(vector->x <= vector->z))
  151.     {
  152.       t1 = -(min->x - position->x);
  153.       t2 = min->y - position->y;
  154.       CHECK_SMALLER(t1, t2, -vector->x, vector->y);
  155.       t2 = -(max->z - position->z);
  156.       CHECK_SMALLER(t1, t2, -vector->x, -vector->z);
  157.       t1 = -(max->x - position->x);
  158.       t2 = max->y - position->y;
  159.       CHECK_BIGGER(t1, t2, -vector->x, vector->y);
  160.       t2 = -(min->z - position->z);
  161.       CHECK_BIGGER(t1, t2, -vector->x, -vector->z);
  162.       return TRUE;
  163.     } else
  164.     if ((-vector->y <= vector->x) AND(-vector->y <= vector->z))
  165.     {
  166.       t1 = max->y - position->y;
  167.       t2 = -(max->x - position->x);
  168.       CHECK_SMALLER(t1, t2, vector->y, -vector->x);
  169.       t2 = -(max->z - position->z);
  170.       CHECK_SMALLER(t1, t2, vector->y, -vector->z);
  171.       t1 = min->y - position->y;
  172.       t2 = -(min->x - position->x);
  173.       CHECK_BIGGER(t1, t2, vector->y, -vector->x);
  174.       t2 = -(min->z - position->z);
  175.       CHECK_BIGGER(t1, t2, vector->y, -vector->z);
  176.       return TRUE;
  177.     } else
  178.     {
  179.       t1 = -(min->z - position->z);
  180.       t2 = -(max->x - position->x);
  181.       CHECK_SMALLER(t1, t2, -vector->z, -vector->x);
  182.       t2 = min->y - position->y;
  183.       CHECK_SMALLER(t1, t2, -vector->z, vector->y);
  184.       t1 = -(max->z - position->z);
  185.       t2 = -(min->x - position->x);
  186.       CHECK_BIGGER(t1, t2, -vector->z, -vector->x);
  187.       t2 = max->y - position->y;
  188.       CHECK_BIGGER(t1, t2, -vector->z, vector->y);
  189.       return TRUE;
  190.     }
  191.   case 3:
  192.     if ((max->x < position->x) OR(max->y < position->y)
  193.         OR(min->z >= position->z))
  194.       return FALSE;
  195.     if ((vector->x >= vector->y) AND(vector->x >= -vector->z))
  196.     {
  197.       t1 = max->x - position->x;
  198.       t2 = min->y - position->y;
  199.       CHECK_SMALLER(t1, t2, vector->x, vector->y);
  200.       t2 = -(max->z - position->z);
  201.       CHECK_SMALLER(t1, t2, vector->x, -vector->z);
  202.       t1 = min->x - position->x;
  203.       t2 = max->y - position->y;
  204.       CHECK_BIGGER(t1, t2, vector->x, vector->y);
  205.       t2 = -(min->z - position->z);
  206.       CHECK_BIGGER(t1, t2, vector->x, -vector->z);
  207.       return TRUE;
  208.     } else
  209.     if ((vector->y >= vector->x) AND(vector->y >= -vector->z))
  210.     {
  211.       t1 = max->y - position->y;
  212.       t2 = min->x - position->x;
  213.       CHECK_SMALLER(t1, t2, vector->y, vector->x);
  214.       t2 = -(max->z - position->z);
  215.       CHECK_SMALLER(t1, t2, vector->y, -vector->z);
  216.       t1 = min->y - position->y;
  217.       t2 = max->x - position->x;
  218.       CHECK_BIGGER(t1, t2, vector->y, vector->x);
  219.       t2 = -(min->z - position->z);
  220.       CHECK_BIGGER(t1, t2, vector->y, -vector->z);
  221.       return TRUE;
  222.     } else
  223.     {
  224.       t1 = -(min->z - position->z);
  225.       t2 = min->x - position->x;
  226.       CHECK_SMALLER(t1, t2, -vector->z, vector->x);
  227.       t2 = min->y - position->y;
  228.       CHECK_SMALLER(t1, t2, -vector->z, vector->y);
  229.       t1 = -(max->z - position->z);
  230.       t2 = max->x - position->x;
  231.       CHECK_BIGGER(t1, t2, -vector->z, vector->x);
  232.       t2 = max->y - position->y;
  233.       CHECK_BIGGER(t1, t2, -vector->z, vector->y);
  234.       return TRUE;
  235.     }
  236.   case 4:
  237.     if ((min->x >= position->x) OR(min->y >= position->y)
  238.         OR(max->z < position->z))
  239.       return FALSE;
  240.     if ((vector->x <= vector->y) AND(vector->x <= -vector->z))
  241.     {
  242.       t1 = -(min->x - position->x);
  243.       t2 = -(max->y - position->y);
  244.       CHECK_SMALLER(t1, t2, -vector->x, -vector->y);
  245.       t2 = min->z - position->z;
  246.       CHECK_SMALLER(t1, t2, -vector->x, vector->z);
  247.       t1 = -(max->x - position->x);
  248.       t2 = -(min->y - position->y);
  249.       CHECK_BIGGER(t1, t2, -vector->x, -vector->y);
  250.       t2 = max->z - position->z;
  251.       CHECK_BIGGER(t1, t2, -vector->x, vector->z);
  252.       return TRUE;
  253.     } else
  254.     if ((vector->y <= vector->x) AND(vector->y <= -vector->z))
  255.     {
  256.       t1 = -(min->y - position->y);
  257.       t2 = -(max->x - position->x);
  258.       CHECK_SMALLER(t1, t2, -vector->y, -vector->x);
  259.       t2 = min->z - position->z;
  260.       CHECK_SMALLER(t1, t2, -vector->y, vector->z);
  261.       t1 = -(max->y - position->y);
  262.       t2 = -(min->x - position->x);
  263.       CHECK_BIGGER(t1, t2, -vector->y, -vector->x);
  264.       t2 = max->z - position->z;
  265.       CHECK_BIGGER(t1, t2, -vector->y, vector->z);
  266.       return TRUE;
  267.     } else
  268.     {
  269.       t1 = max->z - position->z;
  270.       t2 = -(max->x - position->x);
  271.       CHECK_SMALLER(t1, t2, vector->z, -vector->x);
  272.       t2 = -(max->y - position->y);
  273.       CHECK_SMALLER(t1, t2, vector->z, -vector->y);
  274.       t1 = min->z - position->z;
  275.       t2 = -(min->x - position->x);
  276.       CHECK_BIGGER(t1, t2, vector->z, -vector->x);
  277.       t2 = -(min->y - position->y);
  278.       CHECK_BIGGER(t1, t2, vector->z, -vector->y);
  279.       return TRUE;
  280.     }
  281.   case 5:
  282.     if ((max->x < position->x) OR(min->y >= position->y)
  283.         OR(max->z < position->z))
  284.       return FALSE;
  285.     if ((vector->x >= -vector->y) AND(vector->x >= vector->z))
  286.     {
  287.       t1 = max->x - position->x;
  288.       t2 = -(max->y - position->y);
  289.       CHECK_SMALLER(t1, t2, vector->x, -vector->y);
  290.       t2 = min->z - position->z;
  291.       CHECK_SMALLER(t1, t2, vector->x, vector->z);
  292.       t1 = min->x - position->x;
  293.       t2 = -(min->y - position->y);
  294.       CHECK_BIGGER(t1, t2, vector->x, -vector->y);
  295.       t2 = max->z - position->z;
  296.       CHECK_BIGGER(t1, t2, vector->x, vector->z);
  297.       return TRUE;
  298.     } else
  299.     if ((-vector->y >= vector->x) AND(-vector->y >= vector->z))
  300.     {
  301.       t1 = -(min->y - position->y);
  302.       t2 = min->x - position->x;
  303.       CHECK_SMALLER(t1, t2, -vector->y, vector->x);
  304.       t2 = min->z - position->z;
  305.       CHECK_SMALLER(t1, t2, -vector->y, vector->z);
  306.       t1 = -(max->y - position->y);
  307.       t2 = max->x - position->x;
  308.       CHECK_BIGGER(t1, t2, -vector->y, vector->x);
  309.       t2 = max->z - position->z;
  310.       CHECK_BIGGER(t1, t2, -vector->y, vector->z);
  311.       return TRUE;
  312.     } else
  313.     {
  314.       t1 = max->z - position->z;
  315.       t2 = min->x - position->x;
  316.       CHECK_SMALLER(t1, t2, vector->z, vector->x);
  317.       t2 = -(max->y - position->y);
  318.       CHECK_SMALLER(t1, t2, vector->z, -vector->y);
  319.       t1 = min->z - position->z;
  320.       t2 = max->x - position->x;
  321.       CHECK_BIGGER(t1, t2, vector->z, vector->x);
  322.       t2 = -(min->y - position->y);
  323.       CHECK_BIGGER(t1, t2, vector->z, -vector->y);
  324.       return TRUE;
  325.     }
  326.   case 6:
  327.     if ((min->x >= position->x) OR(max->y < position->y)
  328.         OR(max->z < position->z))
  329.       return FALSE;
  330.     if ((-vector->x >= vector->y) AND(-vector->x >= vector->z))
  331.     {
  332.       t1 = -(min->x - position->x);
  333.       t2 = min->y - position->y;
  334.       CHECK_SMALLER(t1, t2, -vector->x, vector->y);
  335.       t2 = min->z - position->z;
  336.       CHECK_SMALLER(t1, t2, -vector->x, vector->z);
  337.       t1 = -(max->x - position->x);
  338.       t2 = max->y - position->y;
  339.       CHECK_BIGGER(t1, t2, -vector->x, vector->y);
  340.       t2 = max->z - position->z;
  341.       CHECK_BIGGER(t1, t2, -vector->x, vector->z);
  342.       return TRUE;
  343.     } else
  344.     if ((vector->y >= -vector->x) AND(vector->y >= vector->z))
  345.     {
  346.       t1 = max->y - position->y;
  347.       t2 = -(max->x - position->x);
  348.       CHECK_SMALLER(t1, t2, vector->y, -vector->x);
  349.       t2 = min->z - position->z;
  350.       CHECK_SMALLER(t1, t2, vector->y, vector->z);
  351.       t1 = min->y - position->y;
  352.       t2 = -(min->x - position->x);
  353.       CHECK_BIGGER(t1, t2, vector->y, -vector->x);
  354.       t2 = max->z - position->z;
  355.       CHECK_BIGGER(t1, t2, vector->y, vector->z);
  356.       return TRUE;
  357.     } else
  358.     {
  359.       t1 = max->z - position->z;
  360.       t2 = -(max->x - position->x);
  361.       CHECK_SMALLER(t1, t2, vector->z, -vector->x);
  362.       t2 = min->y - position->y;
  363.       CHECK_SMALLER(t1, t2, vector->z, vector->y);
  364.       t1 = min->z - position->z;
  365.       t2 = -(min->x - position->x);
  366.       CHECK_BIGGER(t1, t2, vector->z, -vector->x);
  367.       t2 = max->y - position->y;
  368.       CHECK_BIGGER(t1, t2, vector->z, vector->y);
  369.       return TRUE;
  370.     }
  371.   case 7:
  372.     if ((max->x < position->x) OR(max->y < position->y)
  373.         OR(max->z < position->z))
  374.       return FALSE;
  375.     if ((vector->x >= vector->y) AND(vector->x >= vector->z))
  376.     {
  377.       t1 = max->x - position->x;
  378.       t2 = min->y - position->y;
  379.       CHECK_SMALLER(t1, t2, vector->x, vector->y);
  380.       t2 = min->z - position->z;
  381.       CHECK_SMALLER(t1, t2, vector->x, vector->z);
  382.       t1 = min->x - position->x;
  383.       t2 = max->y - position->y;
  384.       CHECK_BIGGER(t1, t2, vector->x, vector->y);
  385.       t2 = max->z - position->z;
  386.       CHECK_BIGGER(t1, t2, vector->x, vector->z);
  387.       return TRUE;
  388.     } else
  389.     if ((vector->y >= vector->x) AND(vector->y >= vector->z))
  390.     {
  391.       t1 = max->y - position->y;
  392.       t2 = min->x - position->x;
  393.       CHECK_SMALLER(t1, t2, vector->y, vector->x);
  394.       t2 = min->z - position->z;
  395.       CHECK_SMALLER(t1, t2, vector->y, vector->z);
  396.       t1 = min->y - position->y;
  397.       t2 = max->x - position->x;
  398.       CHECK_BIGGER(t1, t2, vector->y, vector->x);
  399.       t2 = max->z - position->z;
  400.       CHECK_BIGGER(t1, t2, vector->y, vector->z);
  401.       return TRUE;
  402.     } else
  403.     {
  404.       t1 = max->z - position->z;
  405.       t2 = min->x - position->x;
  406.       CHECK_SMALLER(t1, t2, vector->z, vector->x);
  407.       t2 = min->y - position->y;
  408.       CHECK_SMALLER(t1, t2, vector->z, vector->y);
  409.       t1 = min->z - position->z;
  410.       t2 = max->x - position->x;
  411.       CHECK_BIGGER(t1, t2, vector->z, vector->x);
  412.       t2 = max->y - position->y;
  413.       CHECK_BIGGER(t1, t2, vector->z, vector->y);
  414.       return TRUE;
  415.     }
  416.   }
  417.   return FALSE;
  418. }
  419. real
  420. bound_intersect(position, vector, min, max)
  421.   REG xyz_ptr     position, vector, min, max;
  422. {
  423.   REG real        distance;
  424.   xyz_struct      p, size;
  425.  
  426.   if ((position->x + ROUNDOFF >= min->x)
  427.       AND(position->x - ROUNDOFF <= max->x)
  428.       AND(position->y + ROUNDOFF >= min->y)
  429.       AND(position->y - ROUNDOFF <= max->y)
  430.       AND(position->z + ROUNDOFF >= min->z)
  431.       AND(position->z - ROUNDOFF <= max->z))
  432.     return ROUNDOFF;
  433.   REALINC(bound_tests);
  434.   p.x = position->x - (max->x + min->x) * 0.5;
  435.   p.y = position->y - (max->y + min->y) * 0.5;
  436.   p.z = position->z - (max->z + min->z) * 0.5;
  437.   size.x = (max->x - min->x) * 0.5;
  438.   size.y = (max->y - min->y) * 0.5;
  439.   size.z = (max->z - min->z) * 0.5;
  440.   if ((vector->x <= -ROUNDOFF) AND(position->x > max->x))
  441.   {
  442.     distance = (size.x - p.x) / vector->x;
  443.     if (distance > 0.0)
  444.       if ((ABS(p.y + distance * vector->y) <= size.y)
  445.           AND(ABS(p.z + distance * vector->z) <= size.z))
  446.         return distance;
  447.   }
  448.   if ((vector->x >= ROUNDOFF) AND(position->x < min->x))
  449.   {
  450.     distance = (-size.x - p.x) / vector->x;
  451.     if (distance > 0.0)
  452.       if ((ABS(p.y + distance * vector->y) <= size.y)
  453.           AND(ABS(p.z + distance * vector->z) <= size.z))
  454.         return distance;
  455.   }
  456.   if ((vector->y <= -ROUNDOFF) AND(position->y > max->y))
  457.   {
  458.     distance = (size.y - p.y) / vector->y;
  459.     if (distance > 0.0)
  460.       if ((ABS(p.x + distance * vector->x) <= size.x)
  461.           AND(ABS(p.z + distance * vector->z) <= size.z))
  462.         return distance;
  463.   }
  464.   if ((vector->y >= ROUNDOFF) AND(position->y < min->y))
  465.   {
  466.     distance = (-size.y - p.y) / vector->y;
  467.     if (distance > 0.0)
  468.       if ((ABS(p.x + distance * vector->x) <= size.x)
  469.           AND(ABS(p.z + distance * vector->z) <= size.z))
  470.         return distance;
  471.   }
  472.   if ((vector->z <= -ROUNDOFF) AND(position->z > max->z))
  473.   {
  474.     distance = (size.z - p.z) / vector->z;
  475.     if (distance > 0.0)
  476.       if ((ABS(p.x + distance * vector->x) <= size.x)
  477.           AND(ABS(p.y + distance * vector->y) <= size.y))
  478.         return distance;
  479.   }
  480.   if ((vector->z >= ROUNDOFF) AND(position->z < min->z))
  481.   {
  482.     distance = (-size.z - p.z) / vector->z;
  483.     if (distance > 0.0)
  484.       if ((ABS(p.x + distance * vector->x) <= size.x)
  485.           AND(ABS(p.y + distance * vector->y) <= size.y))
  486.         return distance;
  487.   }
  488.   return 0.0;
  489. }
  490. void
  491. cluster_intersect(octant, source_id, cached_id, position, vector, cluster,
  492.                   max_distance, intersect_id, change)
  493.   int             octant, source_id, cached_id;
  494.   REG xyz_ptr     position, vector;
  495.   cluster_ptr     cluster;
  496.   real           *max_distance;
  497.   int            *intersect_id;
  498.   boolean         change;
  499. {
  500.   REG int         i;
  501.   REG real        distance;
  502.   object_ptr      object;
  503.  
  504.   for (i = 0; i < cluster->size; POSINC(i))
  505.   {
  506.     object = (object_ptr) (cluster->object[i]);
  507.     if (((object->id == source_id) OR(object->id == cached_id))
  508.         AND CONVEX(object->object_type)
  509.         AND(NOT COLOR_BIG(surface[object->surface_id]->transparent, ROUNDOFF)
  510.             OR NOT SELF_INTERSECT(object->object_type, TRUE)))
  511.       continue;
  512.     if (NOT octant_intersect(octant, position, vector,
  513.                              object->min, object->max))
  514.       continue;
  515.     if (CHECK_BOUNDS(object->object_type))
  516.     {
  517.       distance = bound_intersect(position, vector, object->min, object->max);
  518.       if ((distance <= 0.0) OR(distance >= *max_distance))
  519.         continue;
  520.     } else
  521.     {
  522.       OBJECT_INTERSECT(distance, position, vector, object);
  523.       if ((distance <= 0.0) OR(distance >= *max_distance))
  524.         continue;
  525.       if (change)
  526.       {
  527.         *intersect_id = object->id;
  528.         *max_distance = distance;
  529.       }
  530.     }
  531.     if (object->object_type == CLUSTER_TYPE)
  532.       cluster_intersect(octant, source_id, cached_id, position, vector,
  533.                         (cluster_ptr) object->data, max_distance,
  534.                         intersect_id, change);
  535.     else
  536.       pqueue_insert(distance, object);
  537.   }
  538. }
  539. void
  540. reset_ray_cache(level, node)
  541.   REG int         level, node;
  542. {
  543.   REG int         next;
  544.  
  545.   ray_cache[node] = NO_OBJECTS;
  546.   next = 1 SHL level;
  547.   POSINC(level);
  548.   if (level < RAY_CACHE_LEVEL_MAX)
  549.   {
  550.     node += next;
  551.     if (ray_cache[node] != NO_OBJECTS)
  552.       reset_ray_cache(level, node);
  553.     node += next;
  554.     if (ray_cache[node] != NO_OBJECTS)
  555.       reset_ray_cache(level, node);
  556.   }
  557. }
  558. real
  559. intersect_all(source_id, position, ray, color)
  560.   int             source_id;
  561.   xyz_ptr         position;
  562.   ray_ptr         ray;
  563.   rgb_ptr         color;
  564. {
  565.   REG boolean     intersect;
  566.   REG int         octant, intersect_id;
  567.   int             id;
  568.   real            distance, small_distance;
  569.   REG real        max_distance;
  570.   xyz_struct      vector, hit, normal;
  571.   object_ptr      intersect_object;
  572.  
  573.   STRUCT_ASSIGN(vector, ray->vector);
  574.   FIND_OCTANT(octant, vector);
  575.   PQUEUE_INITIALIZE;
  576.   /* Check cached object */
  577.   if ((shade_level < RAY_CACHE_LEVEL_MAX)
  578.       AND(ray_cache[ray_node] != NO_OBJECTS))
  579.   {
  580.     intersect_object = object[ray_cache[ray_node]];
  581.     intersect = octant_intersect(octant, position, &vector,
  582.                                  intersect_object->min, intersect_object->max);
  583.     if (intersect AND CHECK_BOUNDS(intersect_object->object_type))
  584.       intersect = (boolean)
  585.         (bound_intersect(position, &vector, intersect_object->min,
  586.                          intersect_object->max) > 0.0);
  587.     if (intersect)
  588.     {
  589.       OBJECT_INTERSECT(max_distance, position, &vector, intersect_object);
  590.       intersect = (boolean) (max_distance > 0.0);
  591.     }
  592.     if (intersect)
  593.       REALINC(ray_cache_hits);
  594.     else
  595.     {
  596.       REALINC(ray_cache_resets);
  597.       max_distance = INFINITY;
  598.       reset_ray_cache(shade_level, ray_node);
  599.     }
  600.     intersect_id = ray_cache[ray_node];
  601.   } else
  602.   {
  603.     max_distance = INFINITY;
  604.     intersect_id = NO_OBJECTS;
  605.   }
  606.   /* Start with root object */
  607.   intersect = octant_intersect(octant, position, &vector,
  608.                                ROOT_OBJECT->min, ROOT_OBJECT->max);
  609.   if (intersect)
  610.     intersect = (boolean)
  611.       (bound_intersect(position, &vector, ROOT_OBJECT->min,
  612.                        ROOT_OBJECT->max) > 0.0);
  613.   if (intersect)
  614.   {
  615.     small_distance = max_distance;
  616.     id = intersect_id;
  617.     cluster_intersect(octant, source_id, intersect_id, position, &vector,
  618.                       (cluster_ptr) ROOT_OBJECT->data, &small_distance,
  619.                       &id, TRUE);
  620.     if (id != intersect_id)
  621.       intersect_id = id;
  622.     while (PQUEUE_NOT_EMPTY)
  623.     {
  624.       pqueue_extract(&distance, &intersect_object);
  625.       if (distance > small_distance)
  626.         break;
  627.       if (CHECK_BOUNDS(intersect_object->object_type))
  628.         OBJECT_INTERSECT(distance, position, &vector, intersect_object);
  629.       if ((distance > 0.0) AND(distance < small_distance))
  630.       {
  631.         REALINC(ray_hits);
  632.         intersect_id = intersect_object->id;
  633.         small_distance = distance;
  634.       }
  635.     }
  636.   }
  637.   if (shade_level < RAY_CACHE_LEVEL_MAX)
  638.     ray_cache[ray_node] = intersect_id;
  639.   if (intersect_id == NO_OBJECTS)
  640.     return 0.0;
  641.   hit.x = position->x + small_distance * vector.x;
  642.   hit.y = position->y + small_distance * vector.y;
  643.   hit.z = position->z + small_distance * vector.z;
  644.   intersect_object = object[intersect_id];
  645.   OBJECT_NORMAL(&hit, intersect_object, &normal);
  646.   shade(&hit, &normal, ray, intersect_object, color);
  647.   ATTEN_COLOR(small_distance, TRUE, TRUE, TRUE, *color, *color);
  648.   return small_distance;
  649. }
  650.